#include <iostream>
#include <vector>
#include <string>

using namespace std;

int findLCS(string t){
    // 查找最长公共子串需要循环n-1次
    for(int n = 1; n < t.size(); n++){
        int i = 0, j = n;
        while(j < t.size()){
            if(t[i] == t[j]){
                i++; j++;
            }else{
                break;
            }
        }
        // 若找到则为最长
        if(j == t.size()) return i;
    }
    return 0;
}

int KMP(string s, string t) {
    vector<int> next = {0};
    for(int i = 1; i < t.size(); i++){
        next.push_back(findLCS(t.substr(0, i))+1);
    }
    int i = 0, j = 0;
    while(i < s.size()){
        if(s[i] == t[j]){
            i++; j++;
        }else{
            if(next[j] == 0){
                i++; j = 0;
            }else{
                j = next[j]-1;
            }
        }
        if(j == t.size()) return i-j;
    }
    return -1;
}

int main(){
    string s = "abbabbababaaababaaa", t = "bbaba";
    cout << KMP(s, t) << endl;
    // cout << findLCS(t) << endl;
    return 0;
}
